#include <stdio.h>
#include <stdlib.h>
#include "E:\Desktop\data_struct\6Graph\2_Adjacency_Matrix\Adj_Matrix.h"
#include "E:\Desktop\data_struct\5TREE\1_bin_tree\creat.h"

void creat_dfstree(Adj_Matrix &G)
{
	int weight_matrix[MAX][MAX] = {
		/*		 0, 1, 2, 3, 4, 5, 6, 7*/
		{0, 2, 2, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY},					  //0
		{2, 0, INFINITY, 2, 2, INFINITY, INFINITY, INFINITY},							  //1
		{2, INFINITY, 0, INFINITY, INFINITY, 2, 2, INFINITY},							  //2
		{INFINITY, 2, INFINITY, 0, INFINITY, INFINITY, INFINITY, 2},					  //3
		{INFINITY, 2, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 2},				  //4
		{INFINITY, INFINITY, 2, INFINITY, INFINITY, 0, 2, INFINITY},					  //5
		{INFINITY, INFINITY, 2, INFINITY, INFINITY, 2, 0, INFINITY},					  //6
		{INFINITY, INFINITY, INFINITY, 2, 2, INFINITY, INFINITY, 0},					  //7
		{INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY}, //8
		{INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY}  //9
	};
	for (int i = 0; i < MAX; i++)
	{
		for (int j = 0; j < MAX; j++)
		{
			G.M[i][j] = weight_matrix[i][j];
		}
	}
	G.node_num = 10;
}

void dfs_forest(Adj_Matrix G, tree *&T)
{
	tree *s1[100];
	int s2[100];
	int top = -1;
	int visited[100] = {0};
	for (int i = 0; i < G.node_num; i++)
	{
		if (!visited[i])
		{
			tree *tp = NULL;
			tp = (tree *)malloc(sizeof(tree));
			tp->data = i;
			tp->left = tp->right = NULL;

			tree *b;
			if (!T)
				T = tp;
			else
			{
				b->right = tp;
			}
			b = tp;

			s1[++top] = tp;
			s2[top] = i;

			while (top >= 0)
			{
				int p = s2[top];
				tree *t = s1[top];
				visited[p] = 1;

				int w;
				for (w = 0; w < G.node_num; w++)
				{
					if (G.M[p][w] != 0 && G.M[p][w] != INFINITY)
					{
						if (!visited[w])
							break;
					}
				}
				if (w < G.node_num)
				{
					s2[++top] = w;
					tree *node = (tree *)malloc(sizeof(tree));
					node->data = w;
					node->left = node->right = NULL;
					if (!t->left)
					{
						t->left = node;
					}
					else
					{
						tree *q = t->left;
						while (q->right)
						{
							q = q->right;
						}
						q->right = node;
					}
					s1[top] = node;
				}
				else
				{
					top--;
				}
			}
		}
	}
}

int visited[100] = {0};
void dfs(Adj_Matrix G, int v, tree *&T)
{
	int frist = 1;
	int w;
	for (w = 0; w < G.node_num; w++)
	{
		if (G.M[v][w] != 0 && G.M[v][w] != INFINITY)
		{
			if (!visited[w])
				break;
		}
	}
	if (w < G.node_num)
	{
		tree *p = (tree *)malloc(sizeof(tree));
	}
}
void dfs_froest(Adj_Matrix G, tree *&T)
{
	tree *q;
	T = NULL;
	for (int i = 0; i < G.node_num; i++)
	{
		if (!visited[i])
		{
			visited[i] = 0;
			tree *p = (tree *)malloc(sizeof(tree));
			p->data = i;
			p->left = p->right = NULL;
			if (!T)
			{
				T = p;
			}
			else
			{
				q->right = p;
			}
			q = p;
			dfs(G, i, p);
		}
	}
}
int main()
{
	/*******************code*******************/
	Adj_Matrix G;
	creat_dfstree(G);
	tree *T = NULL;
	dfs_forest(G, T);
	midorder_traversal(T);
	/******************************************/
	printf("\n\n****************************\n");
	printf("Press Enter key to continue\n");
	getchar();
	return 0;
	/******************************************/
}
